Placement is one of the most fundamental problems in physical design flow since it assigns exact locations for various circuit components within the chip's core area. An inferior placement of the components may not only affect the chip's performance but also its manufacturability. For example, inferior placement assignment may produce excessive wirelength which may be beyond the available routing resources. As a result, the placer must perform such assignment while optimizing one or more objectives of the circuit to ensure that it meets the design requirements such as wirelength, density, power, timing, and many others.
A placer generally takes a netlist from logic synthesis and a technology library to produce a placement layout. The netlist is typically composed of a number of nets together with various components such as standard cells, macro blocks, or I/O pads. There have been several established techniques for standard cell placement, macro placement, and floorplanning with different objectives taken into account. Current placement approaches typically fall into the following categories: (1) minimum cut/partitioning based methods, (2) quadratic programming based methods, (3) force based placement methods, (4) analytic placement methods, and (5) simulated annealing based methods.
A minimum cut/partitioning placer recursively partitions, in a top down hierarchical fashion, a netlist into 2n partitions, where n≧1. In addition to partitioning a netlist into partitions, a minimum cut/partitioning placer also recursively subdivides the layout area into a number of bins and assigns each of the netlist partitions into one of the bins. A bisection is achieved through either a horizontal or a vertical cut through the layout area during bin dividing. A quadrisection is achieved through simultaneous horizontal and vertical cuts through the layout area.
Quadratic programming based methods seek to minimize quadratic wirelength objectives or to optimize other quadratic objectives. Compared to the other placement/floorplanning methods, the quadratic programming based methods are relatively fast, and the stability is reasonably good. The quality of the results is, however, inconsistent.
In the conventional force-directed placement method, the forces are related to the number of connections among the modules. Based upon some criteria such as the area density of the placement, the force-based placement methods add wire length dependent forces or other additional forces to the cells to consider the placement area and particularly to reduce cell overlaps. Such force-based or force-directed placement methods seem to give good stability with quality of the results inferior to that of the analytical methods. The drawback on the force-based methods is that such methods tend to be very slow in reaching the final results.
The analytic placement methods capture the placement problems mathematically and use efficient numerical solvers to solve the problems within practical runtime. Although analytic placement methods usually exhibit good stability and give arguably the best quality final results, these methods tend to converge at a much slower speed than the min-cut/partitioning based placement methods or the quadratic programming based methods do.
Simulated annealing methods generally start from an initial configuration and iteratively move towards new configurations by displacing, swapping, or reorienting the cells until some criteria are met. During each iteration, a random transition from the current configuration to a new configuration is generated. Such a transition is accepted if, as a result of this transition, one or more objectives of the circuit is probabilistically improved. Otherwise, such a transition is probabilistically rejected. These simulated annealing methods not only do not significantly improve the netlength, but also tend to reach the final results at an extremely slow speed.
However, partitioning based methods tend to be fast but exhibit low stability and inconsistent quality. Quadratic programming based placers, although slower than partitioning based methods, are relatively fast and exhibit good stability with respect to input changes. Their quality, however, is generally inferior to that of analytic methods. Force based placers provide very good stability but are relatively slow and do not work well in the presence of large blocks. Their quality typically lags behind that of analytic placement engines. Simulated annealing based placement methods are extremely slow without significantly improving the netlength. Analytic methods tend to have the best netlength on practical designs but are generally much slower than partitioning or quadratic programming based methods, and the incorporation of different objectives is relatively hard. They tend to perform sub-optimally on designs with regular structure.
Thus, a need exists for a method, system, and computer program product for a fast and stable placement/floorplanning method that gives consistent and good quality results. Various embodiments of the present invention provide a method and system for approximate placement of various standard cells, macro-blocks, and I/O pads for the design of integrated circuits by approximating the final shapes of the objects of interest by one or more probability distribution functions over the areas for the objects of interest with improved runtime and very good stability. These probability distributions are gradually localized to final shapes satisfying the placement constraints and optimizing an objective function.
In some embodiments of the present invention, the aforementioned methods also estimate the final quality of the placement of various standard cells, macro-blocks, and I/O pads. Yet in some other embodiments of the present invention, the aforementioned methods are interleaved with global optimization steps to optimize various objectives according to currently available information and can be naturally combined with the multi-level paradigm. Aside from the advantages of improved runtime and stability, various embodiments of the present invention also allow for incorporating difficult constraints and/or objective functions. Furthermore, although various embodiments of the present invention find their application primarily in electronic design automation, some embodiments of the present invention in other applications where the locations of objects within a specified region or space need to be determined such that the locations optimize some cost functions.
Further details of aspects, objects, and advantages of some embodiments of the invention are described below in the detailed description, drawings, and claims. Both the foregoing general description and the following detailed description are exemplary and explanatory, and are not intended to be limiting as to the scope of various embodiments of the invention.